import java.util.Arrays;

/**
 * 169.多数元素
 */
public class Exerciser3 {
    /**
     * 进阶情况
     */
    public int majorityElement(int[] nums) {
        // 摩尔投票法
        // 统计每个数出现的次数，如果和当前众数不一样的话，那么就把当前众数出现的次数减1，如果和当前众数一致，就进行加1
        // 如果出现众数，那么这个众数的个数一定比其余的数加起来的出现的次数都多，所以最后的就是要的众数
        // 这个题是，必存在众数，可以直接返回，如果没有说，那么需要进行判断
        int n = nums.length;
        int count = 0;
        int ret = 0;
        for(int x : nums) {
            if(count == 0) {
                ret = x;
            }
            count += ret == x ? 1 : -1;
        }
        // 进行判断是否是众数
        int m = 0;
        for(int x : nums) {
            if(ret == x) {
                m++;
            }
        }
        return m >= n / 2 ? ret : 0;
    }

    /**
     * 最优解法：摩尔投票法
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        int n = nums.length;
        int count = 0;
        int ret = 0;
        for(int x : nums) {
            if(count == 0) {
                ret = x;
            }
            count += ret == x ? 1 : -1;
        }
        return ret;
    }

    public int majorityElement1(int[] nums) {
        // 方法1：对于数组进行排序，其中值即为众数(出现最多的数)，因为这个题是一定存在众数的所以可以这样做
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
